`
https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/
`

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var validSubstringCount = function (word1, word2) {
  // 本题是 LC 76. 最小覆盖子串 的求个数版本
  const n = word1.length
  const needs = new Map()
  for (const c of word2) {
    needs.set(c, (needs.get(c) || 0) + 1)
  }
  const cnt = new Map()
  let count = 0
  let res = 0
  let left = 0, right = 0

  while (right < n) {
    const c = word1[right++]
    const cc = cnt.get(c) || 0
    cnt.set(c, cc + 1)
    if (cc + 1 === needs.get(c)) count++

    // 关注 left - 1 的合法性
    while (count === needs.size) {
      const d = word1[left++]
      const dc = cnt.get(d)
      if (dc === needs.get(d)) count--
      cnt.set(d, dc - 1)
    }

    // 窗口内的子串加上 left 之前的所有字符拼接成的子串都是答案，有 left 个
    res += left
  }

  return res
};